home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Mac Game Programming Gurus / TricksOfTheMacGameProgrammingGurus.iso / CodeWarrior Lite / Metrowerks C⁄C++ Lite / Headers / STL Headers / deque.h < prev    next >
Encoding:
C/C++ Source or Header  |  1995-03-06  |  15.7 KB  |  545 lines  |  [TEXT/MMCC]
  1. /*
  2.  *
  3.  * Copyright (c) 1994
  4.  * Hewlett-Packard Company
  5.  *
  6.  * Permission to use, copy, modify, distribute and sell this software
  7.  * and its documentation for any purpose is hereby granted without fee,
  8.  * provided that the above copyright notice appear in all copies and
  9.  * that both that copyright notice and this permission notice appear
  10.  * in supporting documentation.  Hewlett-Packard Company makes no
  11.  * representations about the suitability of this software for any
  12.  * purpose.  It is provided "as is" without express or implied warranty.
  13.  *
  14.  */
  15.  
  16. #ifndef DEQUE_H
  17. #define DEQUE_H
  18.  
  19. #include <function.h>
  20. #include <algobase.h>
  21. #include <iterator.h>
  22. #include <bool.h>
  23.  
  24. #ifndef Allocator
  25. #define Allocator allocator
  26. #include <defalloc.h>
  27. #endif
  28.  
  29. #ifndef deque 
  30. #define deque deque
  31. #endif
  32.  
  33. template <class T> 
  34. class deque {
  35. public:
  36.     class iterator;
  37.     class const_iterator;
  38.     friend class iterator;
  39.     friend class const_iterator;
  40. public:
  41.     typedef T value_type;
  42.     typedef Allocator<T> data_allocator_type;
  43.     typedef Allocator<T>::pointer pointer;
  44.     typedef Allocator<T>::reference reference;
  45.     typedef Allocator<T>::const_reference const_reference;
  46.     typedef Allocator<T>::size_type size_type;
  47.     typedef Allocator<T>::difference_type difference_type;
  48.     typedef Allocator<pointer> map_allocator_type;   
  49. protected:
  50.     static data_allocator_type data_allocator;
  51.     static size_type buffer_size;
  52.     static map_allocator_type map_allocator;
  53.     typedef Allocator<pointer>::pointer map_pointer;
  54. public:
  55.     class iterator : public random_access_iterator<T, difference_type> {
  56.     friend class deque<T>;
  57.     friend class const_iterator;
  58.     protected:
  59.     pointer current;
  60.     pointer first;
  61.     pointer last;
  62.     map_pointer node;
  63.     iterator(pointer x, map_pointer y) 
  64.         : current(x), first(*y), last(*y + buffer_size), node(y) {}
  65.     public:
  66.     iterator() : current(0), first(0), last(0), node(0) {}
  67.     reference operator*() const { return *current; }
  68.     difference_type operator-(const iterator& x) const {
  69.         return node == x.node 
  70.         ? current - x.current 
  71.         : difference_type(buffer_size * (node - x.node - 1) +
  72.                   (current - first) + (x.last - x.current));
  73.     }
  74.     iterator& operator++() {
  75.         if (++current == last) {
  76.         first = *(++node);
  77.         current = first;
  78.         last = first + buffer_size;
  79.         }
  80.         return *this; 
  81.     }
  82.     iterator operator++(int)  {
  83.         iterator tmp = *this;
  84.         ++*this;
  85.         return tmp;
  86.     }
  87.     iterator& operator--() {
  88.         if (current == first) {
  89.         first = *(--node);
  90.         last = first + buffer_size;
  91.         current = last;
  92.         }
  93.         --current;
  94.         return *this;
  95.     }
  96.     iterator operator--(int) {
  97.         iterator tmp = *this;
  98.         --*this;
  99.         return tmp;
  100.     }
  101.     iterator& operator+=(difference_type n) {
  102.         difference_type offset = n + (current - first);
  103.         difference_type num_node_to_jump = offset >= 0
  104.         ? offset / buffer_size
  105.         : -((-offset + buffer_size - 1) / buffer_size);
  106.         if (num_node_to_jump == 0)
  107.         current += n;
  108.         else {
  109.         node = node + num_node_to_jump;
  110.         first = *node;
  111.         last = first + buffer_size;
  112.         current = first + (offset - num_node_to_jump * buffer_size);
  113.         }
  114.         return *this;
  115.     }
  116.     iterator& operator-=(difference_type n) { return *this += -n; }
  117.     iterator operator+(difference_type n) const {
  118.         iterator tmp = *this;
  119.         return tmp += n;
  120.     }
  121.     iterator operator-(difference_type n) const {
  122.         iterator tmp = *this;
  123.         return tmp -= n;
  124.     }
  125.     reference operator[](difference_type n) { return *(*this + n); }
  126.     bool operator==(const iterator& x) const {      
  127.         return current == x.current || 
  128.         ((current == first || x.current == x.first) && 
  129.          *this - x == 0);
  130.     }
  131.     bool operator<(const iterator& x) const {
  132.         return (node == x.node) ? (current < x.current) : (node < x.node);
  133.     }
  134.     };
  135.     class const_iterator : public random_access_iterator<T, difference_type> {
  136.     friend class deque<T>;
  137.     protected:
  138.     pointer current;
  139.     pointer first;
  140.     pointer last;
  141.     map_pointer node;
  142.     const_iterator(pointer x, map_pointer y) 
  143.         : current(x), first(*y), last(*y + buffer_size), node(y) {}
  144.     public:
  145.     const_iterator() : current(0), first(0), last(0), node(0) {}
  146.     const_iterator(const iterator& x) 
  147.         : current(x.current), first(x.first), last(x.last), node(x.node) {}     
  148.     const_reference operator*() const { return *current; }
  149.     difference_type operator-(const const_iterator& x) const {
  150.         return node == x.node 
  151.         ? current - x.current 
  152.         : difference_type(buffer_size * (node - x.node - 1) +
  153.                   (current - first) + (x.last - x.current));
  154.     }
  155.     const_iterator& operator++() {
  156.         if (++current == last) {
  157.         first = *(++node);
  158.         current = first;
  159.         last = first + buffer_size;
  160.         }
  161.         return *this; 
  162.     }
  163.     const_iterator operator++(int)  {
  164.         const_iterator tmp = *this;
  165.         ++*this;
  166.         return tmp;
  167.     }
  168.     const_iterator& operator--() {
  169.         if (current == first) {
  170.         first = *(--node);
  171.         last = first + buffer_size;
  172.         current = last;
  173.         }
  174.         --current;
  175.         return *this;
  176.     }
  177.     const_iterator operator--(int) {
  178.         const_iterator tmp = *this;
  179.         --*this;
  180.         return tmp;
  181.     }
  182.     const_iterator& operator+=(difference_type n) {
  183.         difference_type offset = n + (current - first);
  184.         difference_type num_node_to_jump = offset >= 0
  185.         ? offset / buffer_size
  186.         : -((-offset + buffer_size - 1) / buffer_size);
  187.         if (num_node_to_jump == 0)
  188.         current += n;
  189.         else {
  190.         node = node + num_node_to_jump;
  191.         first = *node;
  192.         last = first + buffer_size;
  193.         current = first + (offset - num_node_to_jump * buffer_size);
  194.         }
  195.         return *this;
  196.     }
  197.     const_iterator& operator-=(difference_type n) { return *this += -n; }
  198.     const_iterator operator+(difference_type n) const {
  199.         const_iterator tmp = *this;
  200.         return tmp += n;
  201.     }
  202.     const_iterator operator-(difference_type n) const {
  203.         const_iterator tmp = *this;
  204.         return tmp -= n;
  205.     }
  206.     const_reference operator[](difference_type n) { 
  207.         return *(*this + n); 
  208.     }
  209.     bool operator==(const const_iterator& x) const {      
  210.         return current == x.current || 
  211.         ((current == first || x.current == x.first) && 
  212.          *this - x == 0);
  213.     }
  214.     bool operator<(const const_iterator& x) const {
  215.         return (node == x.node) ? (current < x.current) : (node < x.node);
  216.     }
  217.     };
  218.     typedef reverse_iterator<const_iterator, value_type, const_reference, 
  219.                              difference_type>  const_reverse_iterator;
  220.     typedef reverse_iterator<iterator, value_type, reference, difference_type>
  221.         reverse_iterator; 
  222. protected:    
  223.     iterator start;
  224.     iterator finish;
  225.     size_type length;
  226.     map_pointer map;
  227.     size_type map_size;
  228.  
  229.     void allocate_at_begin();
  230.     void allocate_at_end();
  231.     void deallocate_at_begin();
  232.     void deallocate_at_end();
  233.  
  234. public:
  235.     deque() : start(), finish(), length(0), map(0), map_size(0) {
  236.     buffer_size = data_allocator.init_page_size();
  237.     }
  238.     iterator begin() { return start; }
  239.     const_iterator begin() const { return start; }
  240.     iterator end() { return finish; }
  241.     const_iterator end() const { return finish; }
  242.     reverse_iterator rbegin() { return reverse_iterator(end()); }
  243.     const_reverse_iterator rbegin() const { 
  244.         return const_reverse_iterator(end()); 
  245.     }
  246.     reverse_iterator rend() { return reverse_iterator(begin()); }
  247.     const_reverse_iterator rend() const { 
  248.         return const_reverse_iterator(begin()); 
  249.     } 
  250.     bool empty() const { return length == 0; }
  251.     size_type size() const { return length; }
  252.     size_type max_size() const { return data_allocator.max_size(); }
  253.     reference operator[](size_type n) { return *(begin() + n); }
  254.     const_reference operator[](size_type n) const { return *(begin() + n); }
  255.     reference front() { return *begin(); }
  256.     const_reference front() const { return *begin(); }
  257.     reference back() { return *(end() - 1); }
  258.     const_reference back() const { return *(end() - 1); }
  259.     void push_front(const T& x) {
  260.     if (empty() || begin().current == begin().first)
  261.         allocate_at_begin();
  262.     --start.current;
  263.     construct(start.current, x);
  264.     ++length;
  265.     }
  266.     void push_back(const T& x) {
  267.     if (empty() || end().current == end().last)
  268.         allocate_at_end();
  269.     construct(finish.current, x);
  270.     ++finish.current;
  271.     ++length;
  272.     }
  273.     void pop_front() {
  274.     destroy(start.current);
  275.     ++start.current;
  276.     --length; 
  277.     if (empty() || begin().current == begin().last)
  278.         deallocate_at_begin();
  279.     }
  280.     void pop_back() {
  281.     --finish.current;
  282.     destroy(finish.current);
  283.     --length; 
  284.     if (empty() || end().current == end().first)
  285.         deallocate_at_end();
  286.     }
  287.     void swap(deque<T>& x) {
  288.     ::swap(start, x.start);
  289.     ::swap(finish, x.finish);
  290.     ::swap(length, x.length);
  291.     ::swap(map, x.map);
  292.     ::swap(map_size, x.map_size);
  293.     }
  294.     iterator insert(iterator position, const T& x);
  295.     void insert(iterator position, size_type n, const T& x);
  296. //  template <class Iterator> void insert(iterator position,
  297. //                                        Iterator first, Iterator last);
  298.     void insert(iterator position, const T* first, const T* last);
  299.     void erase(iterator position);
  300.     void erase(iterator first, iterator last);    
  301.     deque(size_type n, const T& value = T())
  302.     : start(), finish(), length(0), map(0), map_size(0) {
  303.     buffer_size = data_allocator.init_page_size();  
  304.     insert(begin(), n, value);
  305.     }
  306. //  template <class Iterator> deque(Iterator first, Iterator last);
  307.     deque(const T* first, const T* last)
  308.     : start(), finish(), length(0), map(0), map_size(0) {
  309.     buffer_size = data_allocator.init_page_size();  
  310.     copy(first, last, back_inserter(*this));
  311.     }
  312.     deque(const deque<T>& x)
  313.     : start(), finish(), length(0), map(0), map_size(0) {
  314.     buffer_size = data_allocator.init_page_size();  
  315.     copy(x.begin(), x.end(), back_inserter(*this));
  316.     }
  317.     deque<T>& operator=(const deque<T>& x) {
  318.     if (this != &x)
  319.         if (size() >= x.size()) 
  320.         erase(copy(x.begin(), x.end(), begin()), end());
  321.         else 
  322.         copy(x.begin() + size(), x.end(),
  323.              inserter(*this, copy(x.begin(), x.begin() + size(),
  324.                       begin())));
  325.     return *this;
  326.     }
  327.     ~deque();
  328. };
  329.  
  330. template <class T>
  331. deque<T>::data_allocator_type deque<T>::data_allocator;
  332.  
  333. template <class T>
  334. deque<T>::map_allocator_type deque<T>::map_allocator;
  335.  
  336. template <class T>
  337. deque<T>::size_type deque<T>::buffer_size = 0; 
  338. // should be data_allocator.init_page_size(); // Borland bug
  339.  
  340. template <class T>
  341. bool operator==(const deque<T>& x, const deque<T>& y) {
  342.     return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
  343. }
  344.  
  345. template <class T>
  346. bool operator<(const deque<T>& x, const deque<T>& y) {
  347.     return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
  348. }
  349.  
  350. template <class T>
  351. deque<T>::~deque() { while (!empty()) pop_front(); }     
  352.  
  353. template <class T>
  354. void deque<T>::allocate_at_begin() {
  355.     pointer p = data_allocator.allocate(buffer_size);
  356.     if (!empty()) {
  357.     if (start.node == map) {
  358.         difference_type i = finish.node - start.node;
  359.         map_size = (i + 1) * 2;
  360.         map_pointer tmp = map_allocator.allocate(map_size);
  361.         copy(start.node, finish.node + 1, tmp + map_size / 4 + 1);
  362.         map_allocator.deallocate(map);
  363.         map = tmp;
  364.         map[map_size / 4] = p;
  365.         start = iterator(p + buffer_size, map + map_size / 4);
  366.         finish = iterator(finish.current, map + map_size / 4 + i + 1);
  367.     } else {
  368.         *--start.node = p;
  369.         start = iterator(p + buffer_size, start.node);
  370.     }
  371.     } else {
  372.     map_size = map_allocator.init_page_size();
  373.     map = map_allocator.allocate(map_size);
  374.     map[map_size / 2] = p;
  375.     start = iterator(p + buffer_size / 2 + 1, map + map_size / 2);
  376.     finish = start;
  377.     }
  378. }
  379.  
  380. template <class T>
  381. void deque<T>::allocate_at_end() {
  382.     pointer p = data_allocator.allocate(buffer_size);
  383.     if (!empty()) {
  384.     if (finish.node == map + map_size - 1) {
  385.         difference_type i = finish.node - start.node;
  386.          map_size = (i + 1) * 2;
  387.         map_pointer tmp = map_allocator.allocate(map_size);
  388.         copy(start.node, finish.node + 1, tmp + map_size / 4);
  389.         map_allocator.deallocate(map);
  390.         map = tmp;
  391.          map[map_size / 4 + i + 1] = p;
  392.         start = iterator(start.current, map + map_size / 4);
  393.         finish = iterator(p, map + map_size / 4 + i + 1);
  394.     } else {
  395.         *++finish.node = p;
  396.         finish = iterator(p, finish.node);
  397.     }
  398.     } else {
  399.     map_size = map_allocator.init_page_size();
  400.     map = map_allocator.allocate(map_size);
  401.     map[map_size / 2] = p;
  402.     start = iterator(p + buffer_size / 2, map + map_size / 2);
  403.     finish = start;
  404.     }
  405. }
  406.  
  407. template <class T>
  408. void deque<T>::deallocate_at_begin() {
  409.     data_allocator.deallocate(*start.node++);
  410.     if (empty()) {
  411.     start = iterator();
  412.     finish = start;
  413.     map_allocator.deallocate(map);
  414.     } else
  415.     start = iterator(*start.node, start.node);
  416. }
  417.  
  418. template <class T>
  419. void deque<T>::deallocate_at_end() {
  420.     data_allocator.deallocate(*finish.node--);
  421.     if (empty()) {
  422.     start = iterator();
  423.     finish = start;
  424.     map_allocator.deallocate(map);
  425.     } else
  426.     finish = iterator(*finish.node + buffer_size, finish.node);
  427. }
  428.  
  429. template <class T>
  430. deque<T>::iterator deque<T>::insert(iterator position, const T& x) {
  431.     if (position == begin()) {
  432.     push_front(x);
  433.     return begin();
  434.     } else if (position == end()) {
  435.     push_back(x);
  436.     return end() - 1;
  437.     } else if (end() - position > position - begin()) {
  438.     push_front(*begin());
  439.     copy(begin() + 2, position, begin() + 1); 
  440.     *(position - 1) = x;
  441.     return position - 1;
  442.     } else {
  443.     push_back(*(end() - 1));
  444.     copy_backward(position, end() - 2, end() - 1); 
  445.     *position = x;
  446.     return position;
  447.     }
  448. }
  449.  
  450. template <class T>
  451. void deque<T>::insert(iterator position, size_type n, const T& x) {
  452.     if (end() - position > position - begin()) {
  453.     iterator old_begin = begin();
  454.     if (n > position - old_begin) {
  455.          size_type m = n - (position - old_begin);
  456.         while (m-- > 0) push_front(x);
  457.         iterator i = position;
  458.         while (i != old_begin) push_front(*--i);
  459.         fill(old_begin, position, x);
  460.     } else {
  461.         iterator i = old_begin + n;
  462.         while (i != old_begin) push_front(*--i);
  463.         copy(old_begin + n, position, old_begin);
  464.         fill(position - n, position, x);
  465.     }
  466.     } else {
  467.     iterator old_end = end();
  468.     if (n > old_end - position) {
  469.          size_type m = n - (old_end - position);
  470.         while (m-- > 0) push_back(x);
  471.         iterator i = position;
  472.         while (i != old_end) push_back(*i++);
  473.         fill(position, old_end, x);
  474.     } else {
  475.         iterator i = old_end - n;
  476.         while (i != old_end) push_back(*i++);
  477.         copy_backward(position, old_end - n, old_end);
  478.         fill(position, position + n, x);
  479.     }
  480.     }
  481. }
  482.  
  483. template <class T>
  484. void deque<T>::insert(iterator position, const T* first, const T* last) {
  485.     size_type n = 0;
  486.     distance(first, last, n);
  487.     if (end() - position > position - begin()) {
  488.     iterator old_begin = begin();
  489.     if (n > position - old_begin) {
  490.          const T* m = last - (position - old_begin);
  491.         while (m != first) push_front(*--m);
  492.         iterator i = position;
  493.         while (i != old_begin) push_front(*--i);
  494.         copy(last - (position - old_begin), last, old_begin);
  495.     } else {
  496.         iterator i = old_begin + n;
  497.         while (i != old_begin) push_front(*--i);
  498.         copy(old_begin + n, position, old_begin);
  499.         copy(first, last, position - n);
  500.     }
  501.     } else {
  502.     iterator old_end = end();
  503.     if (n > old_end - position) {
  504.          const T* m = first + (old_end - position);
  505.         while (m != last) push_back(*m++);
  506.         iterator i = position;
  507.         while (i != old_end) push_back(*i++);
  508.          copy(first, first + (old_end - position), position);
  509.     } else {
  510.         iterator i = old_end - n;
  511.         while (i != old_end) push_back(*i++);
  512.         copy_backward(position, old_end - n, old_end);
  513.         copy(first, last, position);
  514.     }
  515.     }
  516. }
  517.  
  518. template <class T>
  519. void deque<T>::erase(iterator position) {
  520.     if (end() - position > position - begin()) {
  521.     copy_backward(begin(), position, position + 1);
  522.     pop_front();
  523.     } else {
  524.     copy(position + 1, end(), position);
  525.     pop_back();
  526.     }
  527. }
  528.     
  529. template <class T>
  530. void deque<T>::erase(iterator first, iterator last) {
  531.      difference_type n = last - first;
  532.     if (end() - last > first - begin()) {
  533.     copy_backward(begin(), first, last);
  534.     while(n-- > 0) pop_front();
  535.     } else   {
  536.     copy(last, end(), first);
  537.     while(n-- > 0) pop_back();
  538.     }
  539. }
  540.  
  541. #undef Allocator
  542. #undef deque
  543.  
  544. #endif
  545.